package com.xxd.algo.leetcode.base;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @author: XiaoDong.Xie
 * @create: 2020-07-03 12:37
 * @description:
 */
public class Question200_Island {
    public int numIslands(char[][] m) {
        if ( (m == null || m[0] == null) || m.length == 0 || m[0].length == 0) {
            return 0;
        }

        List<String> list = new ArrayList<String>();

        for (int row = 0; row < m.length; row++) {
            for (int col = 0; col < m[0].length; col++) {
                if (m[row][col] == '1') {
                    list.add(row + "_" + col);
                }
            }
        }

        UnionFindSet<String> unionSet = new UnionFindSet<>(list);

        for (int row = 0; row < m.length; row++) {
            for (int col = 0; col < m[0].length; col++) {
                if (m[row][col] == '1') {
                    String position = row + "_" + col;
                    // 上边
                    if (row - 1 >= 0 && m[row - 1][col] == '1') {
                        String up = (row - 1) + "_" + col;
                        unionSet.union(position, up);
                    }

                    // 下边
                    if (row + 1 < m.length && m[row + 1][col] == '1') {
                        String down = (row + 1) + "_" + col;
                        unionSet.union(position, down);
                    }

                    // 左边
                    if (col - 1 >= 0 && m[row][col - 1] == '1') {
                        String left = row + "_" + (col - 1);
                        unionSet.union(position, left);
                    }

                    // 右边
                    if (col + 1 > m[0].length && m[row][col + 1] == '1') {
                        String right = row + "_" + (col + 1);
                        unionSet.union(position, right);
                    }
                }
            }
        }

        return unionSet.getSizeMapNum();

    }

    public static class Element<V> {
        V value;

        public Element(V value) {
            this.value = value;
        }
    }

    public static class UnionFindSet<V> {
        // 元素hash表
        public HashMap<V, Element<V>> elementMap;

        // 父
        public HashMap<Element<V>, Element<V>> fatherMap;

        // key 某个集合的代表元素 value 集合的大小
        public HashMap<Element<V>, Integer> sizeMap;

        public UnionFindSet(List<V> list) {
            elementMap = new HashMap<>();
            sizeMap = new HashMap<>();
            fatherMap = new HashMap<>();

            for (V value : list) {
                Element<V> element = new Element<>(value);
                sizeMap.put(element, 1);
                fatherMap.put(element, element);
                elementMap.put(value, element);
            }
        }

        /**
         * 是否是同一个集合
         *
         * @param a
         * @param b
         * @return
         */
        public boolean isSameSet(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
            }
            return false;
        }

        /**
         * 合并两个集合
         *
         * @param a
         * @param b
         */
        public void union(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                Element<V> aF = findHead(elementMap.get(a));
                Element<V> bF = findHead(elementMap.get(b));

                if (aF != bF) { // 两个人不相同，则把小的 挂在 大的上面
                    Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
                    Element<V> small = big == aF ? bF : aF;

                    // 小的代表节点，搞到大的代表节点上面去
                    fatherMap.put(small, big);
                    sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
                    sizeMap.remove(small);
                }
            }
        }

        /**
         * 给一个element ，返回他的代表元素
         *
         * @param element 集合中任意的一个元素
         * @return 代表元素
         */
        private Element<V> findHead(Element<V> element) {
            Stack<Element<V>> path = new Stack<>();
            while (element != fatherMap.get(element)) {
                path.push(element);
                element = fatherMap.get(element);
            }

            while (!path.isEmpty()) {
                fatherMap.put(path.pop(), element);
            }
            return element;
        }

        public int getSizeMapNum() {
            return this.sizeMap.size();
        }
    }
}
